package edu.cmu.cs211.pg.algorithms;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.TreeSet;

import edu.cmu.cs211.pg.graph.Edge;
import edu.cmu.cs211.pg.graph.Graph;

public class BFS
{
	/**
	 * Returns the shortest path on the given graph using Breadth-First Search.
	 * In this case, shortest path is defined as the path that uses the least number of edges.
	 * 
	 * @param g The DIRECTED graph that we are searching for a path on
	 * @param start The vertex that begins the path
	 * @param goal The vertex we are trying to find a path to
	 * @throws IllegalArgumentException if either start or goal is not a vertex in g  
	 * @return A list of Edges that represent a path between start and goal if one exists
	 * 		   Otherwise, returns null
	 */
	
	/* 
	 *This class uses the methods in the MyDirectedGraph class in order to
	 *be able to do a breadth-first search for a goal node given a start node and
	 *a graph.
	 *We used a priorityqueue and arraylist instead of a queue 
	 */
	public <V extends Comparable<V>,E extends Edge<V>> List<E> shortestPath(Graph<V,E> g, V start, V goal)
	{
		/*
		 * checking to make sure everything was properly initialized
		 */
		if(g.vertices().contains(start)!=true || g.vertices().contains(goal)!=true)
			throw new IllegalArgumentException();
		List<V> list=new ArrayList<V>();
		int edges=0;
		List<E> edlist=new ArrayList<E>();
		PriorityQueue<V> q=new PriorityQueue<V>();
		q.add(start);
		while(!q.isEmpty()){
			V vert=q.poll();
			list.add(vert);
			Set<E> edge=(Set<E>) g.outgoingEdges(vert);
			Iterator<E> itr=edge.iterator();
			while(itr.hasNext()){
				E ed=itr.next();
				if(!list.contains(ed.dest())){
					q.add(ed.dest());
					edlist.add(ed);
				   if(ed.dest().equals(goal)){
					break;
				   }
				}
			}	
		}
		
		//check that the graph was connected
		Iterator<V> s = g.vertices().iterator();
		while(s.hasNext()){
			if(!list.contains(s.next()))
				throw new IllegalArgumentException();
		}
		
		/*
		 * if the goal was not found, return null
		 */
		if(!list.contains(goal)) return null; //goal was not found
		List<E> toRet=new ArrayList<E>();
		V dest=goal;
		Object[] arr=edlist.toArray();
		for(int i=arr.length-1; i>=0; i--){
			if(((E)arr[i]).dest().equals(dest)){
				toRet.add((E)arr[i]);
				dest=((E)arr[i]).src();
			}
		}
		
		List<E> toRet2=new ArrayList<E>();
		for(int i=toRet.size()-1; i>=0; i--){
			toRet2.add(toRet.remove(i));
		}
		
		return toRet2;
		
	}
}

